package uk.ac.strath.cis.metric_spaces.indices;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import uk.ac.strath.cis.metric_spaces.framework.AbstractMetricIndex;
import uk.ac.strath.cis.metric_spaces.framework.Distance;
import uk.ac.strath.cis.metric_spaces.framework.MetricIndex;

/**
 * @author Robert
 *
 * @param <E>
 */
public class FixedQueriesTree<E> extends AbstractMetricIndex<E> {

    private int currentLevel;
    private E leaf;
    private final Map<Integer, E> keys = new HashMap<Integer, E>(); // level ->
    // Key
    private final Map<Double, Set<FixedQueriesTree<E>>> children = new HashMap<Double, Set<FixedQueriesTree<E>>>(); // distance

    // ->
    // subtrees

    /**
     * @param d
     */
    public FixedQueriesTree(Distance<E> d) {
        super(d);
        currentLevel = 0;
    }

    /**
     * @param copy
     * @param level
     */
    private FixedQueriesTree(FixedQueriesTree<E> copy, int level) {
        super(copy);
        currentLevel = level;
    }

    /* (non-Javadoc)
     * @see uk.ac.strath.cis.rmoss.metric_spaces.framework.AbstractMetricIndex#insert(java.util.Set)
     */
    public void insert(Set<E> elements) {
        super.insert(elements);
        for (E e : elements) {
            insert(e, this);
        }
    }

    private void insert(E element, FixedQueriesTree<E> subtree) {
        E key = keys.get(subtree.currentLevel);
        if (key == null) {
            keys.put(subtree.currentLevel, element);
            key = element;
        }

        double distance = distance(key, element);
        Set<FixedQueriesTree<E>> set = subtree.children.get(distance);
        if (set == null) {
            set = new HashSet<FixedQueriesTree<E>>();
            subtree.children.put(distance, set);
            addLeaf(element, set, subtree.currentLevel + 1);
        } else {
            if (set.size() < 2) {
                if (set.isEmpty() || containsLeaves(set)) {
                    addLeaf(element, set, subtree.currentLevel + 1);
                } else {
                    FixedQueriesTree<E> node = set.iterator().next();
                    insert(element, node);
                }
            } else { // bucket now full - make node
                if (!containsLeaves(set)) {
                    throw new AssertionError("Too many nodes in this bucket");
                }
                FixedQueriesTree<E> node = new FixedQueriesTree<E>(this,
                        subtree.currentLevel + 1);
                Collection<FixedQueriesTree<E>> toBeRemoved = new ArrayList<FixedQueriesTree<E>>();
                for (FixedQueriesTree<E> leaf : set) {
                    insert(leaf.leaf, node);
                    toBeRemoved.add(leaf);
                }
                // System.out.println(element +" : "+ node);
                insert(element, node);
                set.removeAll(toBeRemoved);
                set.add(node);
            }
        }

    }

    private void addLeaf(E element, Set<FixedQueriesTree<E>> set, int level) {
        FixedQueriesTree<E> fqt = new FixedQueriesTree<E>(this, level);
        fqt.leaf = element;
        set.add(fqt);
    }

    private boolean containsLeaves(Set<FixedQueriesTree<E>> set) {
        boolean returnValue = true;
        for (FixedQueriesTree<E> tree : set) {
            returnValue = (tree.leaf != null) && returnValue;
        }
        return returnValue;
    }

    /* (non-Javadoc)
     * @see uk.ac.strath.cis.rmoss.metric_spaces.framework.MetricIndex#rangeQuery(java.lang.Object, double)
     */
    public Set<E> rangeQuery(E element, double radius) {
        Set<E> returnSet = new HashSet<E>();
        rangeQuery(returnSet, element, this, radius);
        return returnSet;

    }

    private boolean isLeaf() {
        return leaf != null;
    }

    private void rangeQuery(Set<E> returnSet, E element,
            FixedQueriesTree<E> fqt, double radius) {
        E e = keys.get(fqt.currentLevel);
        e = fqt.isLeaf() ? fqt.leaf : e;
        double distance = distance(element, e);
        if (fqt.isLeaf() && (distance <= radius)) {
            returnSet.add(fqt.leaf);
        }
        Set<Double> keySet = fqt.children.keySet();
        for (double i : keySet) {
            if ((distance - radius <= i) && (i <= distance + radius)) {
                Set<FixedQueriesTree<E>> set = fqt.children.get(i);
                for (FixedQueriesTree<E> child : set) {
                    rangeQuery(returnSet, element, child, radius);
                }
            }
        }

    }

    @SuppressWarnings("unchecked")
    private String toString(StringBuilder sb, FixedQueriesTree<E> node) {
        if (node == null) {
            return "";
        }
        sb.append(node.leaf == null ? "." : node.leaf);
        if (!node.children.isEmpty()) {
            sb.append("(");
            int i = 0;
            for (Object value : node.children.values().toArray()) {
                int j = 0;
                Set<FixedQueriesTree<E>> set = (Set<FixedQueriesTree<E>>) value;
                if (!set.isEmpty()) {
                    sb.append("[");
                    for (FixedQueriesTree<E> child : set) {
                        toString(sb, child);
                        if (j < set.size() - 1) {
                            sb.append(",");
                        }
                        j++;
                    }
                    sb.append("]");
                }
                if (i < node.children.values().size() - 1) {
                    sb.append(",");
                }
                i++;
            }
            sb.append(")");
        }
        return sb.toString();
    }

    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        return this.toString(sb, this);
    }
    
    @Override
    public MetricIndex<E> clone() {
    	return new FixedQueriesTree<E>(this, 0);
    }
}
